package com.code.leetcode._202507;

import java.util.HashSet;
import java.util.Set;

// 52 N皇后II
public class SolveNQueen {
    /**
     * n皇后的问题研究的是如何将n个皇后放置在n*n的棋盘上，并且使皇后批次之间不能相互攻击
     * 给你一个整数你n，返回n皇后问题不同的解决方案的数量
     * 示例1：输入：n=4
     * 输出：2
     * 4皇后问题存在不同的解法
     * 示例2：
     * 输入：n=1
     * 输出：1
     **/
    public static void main(String[] args) {
        SolveNQueen s = new SolveNQueen();
        System.out.println(s.totalNQueens(4));
    }

    /**
     * N皇后问题 研究的使如何将N个皇后放置在N*N的棋盘上，并且使皇后批次之间不能相互攻击。
     * 皇后的走法使：可以横直斜走，格数不限。因此要求皇后彼此之间不能相互攻击，等价于要求任何两个皇后
     * 都不能在同一行、同一列以及同一条斜线上。
     * 直观的做法使暴力枚举将N个皇后放置在N*N的棋盘上的所有可能的情况，并对每一种情况判断是否满足皇后
     * 彼此之间不相互攻击。暴力枚举的时间复杂度是非常高的，因此必须利用限制条件加以优化。
     * 显然，每个皇后必须位于不同行和不同列，因此将N个皇后放置在N*N的棋盘上，一定是每一个有且仅有一个皇后，
     * 每一列有且仅有一个皇后，且任何两个皇后都不能在同一条斜线上。基于上述发现，可以通过回溯的方式寻找可能的解。
     * 回溯的具体做法是：使用一个数组记录每行放置的皇后的列下标，依次在每一行放置一个皇后。每次新放置的皇后都不能和
     * 已经放置的皇后之间有攻击：即新放置的皇后不能和任何一个已经放置的皇后在同一列以及同一条斜线上，并更新数组中的
     * 当前行的皇后列下标。当N个皇后都放置完毕，则找到一个可能的。当找到一个可能的解之后，将数组转换成表示棋盘状态的
     * 列表，并将该棋盘状态的列表加入返回列表。
     * 由于每个皇后必须位于不同列，因此已经放置的皇后所在的列不能放置别的皇后。第一个皇后有N列可以选择，第二个皇后最多有N-1
     * 列可以选择，第三个皇后最多有N-2列可以选择(如果考虑到不能在同一条斜线上，可能的选择数量更少)，因此所有可能的情况
     * 不会超过N！种，遍历这些情况的时间复杂度O(N!)。
     * 为了降低总时间复杂度，每次放置皇后时需要快速判断每个位置是否可以放置皇后，显然，最理想的情况使在O(1)的时间内判断
     * 该位置所在的列和两条斜线上是否已经有皇后。
     * 以下两种方法分别使用集合和位运算对皇后的放置位置进行判断，都可以在O(1)的时间内判断一个位置是否可以放置皇后，
     * 算法的总时间复杂度都是O(N!)
     * 方法一：基于集合的回溯
     * 为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合columns、diagonals1和diagonals1分别记录每一列以及
     * 两个方向的每条斜线上是否有皇后。
     * 列的表示法很直观，一共有N列，每一列的下标范围从0到N-1，使用列的下标即可明确表示每一列。
     * 如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标和列下标之间的关系。
     * 方向一的斜线从左上到右下方向，同一条斜线上的每个位置满足行下标和列下标之差相等，例如(0,0)和(3,3)在同一条方向一的斜线上。
     * 因此使用行下标和列下标之差既可以明确表示每一条方向一的斜线。
     * 方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等，例如(3,0)和(1,2)在同一条方向二的斜线上
     * 因此使用行下标和列下标之和即可明确表示每一条方向二的斜线
     * 每次放置皇后时，对于每个位置判断其是否在三个集合种，如果三个集合都不包含当前位置，则当前位置时可以放置皇后的位置。
     **/
    public int totalQueens(int n) {
        Set<Integer> columns = new HashSet<>();
        Set<Integer> diagonals1 = new HashSet<>();
        Set<Integer> diagonals2 = new HashSet<>();
        return backtrack(n, 0, columns, diagonals1, diagonals2);
    }

    public int backtrack(int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            return 1;
        } else {
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)) {
                    continue;
                }
                int diagonal1 = row - i;
                if (diagonals1.contains(diagonal1)) {
                    continue;
                }
                int diagonal2 = row + i;
                if (diagonals2.contains(diagonal2)) {
                    continue;
                }
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                count += backtrack(n, row + 1, columns, diagonals1, diagonals2);
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
            return count;
        }
    }

    /**
     * 基于位运算的回溯
     * 方法一使用三个集合分别记录每一列以及两个方向的每条斜线上时候右皇后，每个几个最多包含N个元素，因此集合的空间复杂度是
     * O(N)，如果利用位运算记录皇后的信息，就可以将记录皇后信息的空间夫再度从O(N)降到O(1)
     * 具体做法是，使用三个整数columns，diagonals1和diagonals2分别记录每一列以及两个方向的每条斜线上是否有皇后，每个
     * 整数有N个二进制位。棋盘的每一列对应每个整数的二进制表示中的一个数位，其中期盼的最左列对应每个整数的低二进制位，最右列
     * 对应每个整数的最高二进制位。
     * 那么如何根据每次放置的皇后更新三个整数的值呢？在说具体的计算方法之前，首先说一个例子。
     * 棋盘的边长和皇后的数量N=8,如果棋盘的前两行分别在第2列和第4列放置了皇后(下标从0开始)
     * 如果在下一行放置皇后，哪些位置不能放置呢？我们用0代表可以放置皇后的位置，1代表不能放置皇后的位置。
     * 新放置的皇后不能和任何一个以及放置的皇后在同一列，因此不能放置在第2列和第4列，对应的columns="0010100"
     * 新放置的皇后不能和任何一个已经放置的皇后在同一条方向一的写线上，因此不能放置在第四列和第5列，对应diagonals1="00110000"
     * 其中第4列位其前两行的第2列的皇后往右下移动两步的位置，第5列为其前一行的第4列的皇后往右下移动一步的位置。
     * 新放置的皇后不能和任何一个已经放置的皇后在同一条方向二的斜线上，因此不能放置在第0列和第3列，对应diagonals2="00001001"
     * 其中第0列为其前两行的第2列的皇后往左下移动两步的位置，第3列为其前一行的第4列的皇后往坐下移动一步的位置。
     * 因此可以得到三个整数的计算方法：
     * 初始时，三个整数的值都等于0，表示没有放置任何皇后
     * 在当前行放置皇后，如果皇后放置在第i列，则将三个整数的第i个二进制位的值设位i
     * 进入下一行时，columns的值保持不变，diagonals1左移一位，diagonals2右移一位，由于棋盘的最左列对应每个整数的
     * 最低二进制位，即每个整数的最右二进制位，因此对整数的移位操作方向和对棋盘的移位操作方向相反。
     * 每次放置皇后时，三个整数的按位或运算的结果即位不能放置皇后的位置，其余位置即为可以放置皇后的位置。可以通过
     * (2^n-1)&(~(columns|diagonals1|diagonals2))得到可以放置皇后的位置，然后遍历这些位置，尝试放置皇后并得到
     * 可能的解。
     * 遍历可以放置皇后的位置时，可以利用以下两个按位与运算的性质：
     * x&(-x)可以获得x的二进制表示中的最低为的1的位置
     * x&(x-1)可以将x的二进制表中中的最低为的1置成0
     * 具体做法是，每次获得可以放置皇后的位置中的最低位，并将该位的值置成0，尝试在该位置放置皇后。这样即可遍历每个可以放置皇后的位置。
     **/
    public int totalNQueens(int n) {
        return slove(n, 0, 0, 0, 0);
    }

    public int slove(int n, int row, int columns, int diagonals1, int diagonals2) {
        if (row == n) {
            return 1;
        } else {
            int count = 0;
            int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
            while (availablePositions != 0) {
                int positon = availablePositions & (-availablePositions);
                availablePositions = availablePositions & (availablePositions - 1);
                count += slove(n, row + 1, columns | positon, (diagonals1 | positon) << 1, (diagonals2 | positon) >> 1);
            }
            return count;
        }
    }
}
